package 算法练习;/**
 * @author： li
 * @date： 2022-01-12 14:43
 * @version 1.0
 */
/* */
import java.util.HashSet;
import java.util.Scanner;
public class 动态规划_01背包问题_二进制表示状态 {
    static int ans=Integer.MIN_VALUE;
    static int V;//背包最大体积
    static int n;//物品个数
    static int[] v;//物品的体积
    static int[] w;//物品的价值
    static int[][] dp;//保存背包的状态
    static HashSet<Integer> hashSet = new HashSet<>();
    static int max;//记录最大容量时的最大价值
    static void 求状态的值(int[] a,int p){
        for(int i=0;i<1<<n;++i)
            for(int j=0;j<n;++j){
//                int k= (int) Math.pow(2,j);
                int k=1<<j;
                if((i&k)==0)continue;
                dp[p][i]=dp[p][i-k]+a[j];
                break;
            }
    }
    static void 求最大的价值(int value){
        for(int i=1;i<(1<<n);++i){
            int j=(1<<n)-i-1;
            for(int k=j;k>0;k=(k-1)&j){
//                System.out.print("i:"+i+" "+"k:"+k+" ");
                if(dp[0][k]==value)
                    ans=Math.max(dp[1][k],ans);
                hashSet.add(ans);
            }
        }
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        n = in.nextInt();
        V = in.nextInt();
        v = new int[n];
        w = new int[n];
        dp = new int[2][1<<n];
        for(int i=0;i<n;i++){
            v[i]=in.nextInt();
            dp[0][1<<i]=v[i];
            w[i]=in.nextInt();
            dp[1][1<<i]=w[i];
        }
        求状态的值(v,0);
        求状态的值(w,1);
//        for(int i=0;i<2;i++)
//            for(int j=0;j<1<<n;j++) {
//                System.out.print(dp[i][j]+"  ");
//                if(j==(1<<n)-1)
//                    System.out.println(" ");
//            }
        求最大的价值(V);
        if(hashSet.isEmpty()){
            求最大的价值(V-1);
        }else {
            for (int i : hashSet) {
                max = Math.max(i, ans);
                ans = i;
            }
            System.out.println(max);
        }
    }
}
